﻿/*------------------------------------------------
 Author:ShenDuo
 CreatedDate:2019.3.19
 UpdatedDate:
 version:0.1
 ------------------------------------------------*/

using System.Collections.Generic;
using System.Linq;
using TrainsTraining.Model;

namespace TrainsTraining
{
    /// <summary>
    ///     Path planning and processing(Breadth-first algorithm)
    /// </summary>
    public class PathHelper
    {
        /// <summary>
        ///     Global node list
        /// </summary>
        public static List<Node> Nodes { get; } = new List<Node>();

        /// <summary>
        ///     Gets all the paths from the starting point to the end point
        /// </summary>
        /// <param name="startNodeId">starting point</param>
        /// <param name="endNodeId"> end point</param>
        /// <returns>paths</returns>
        internal static List<Path> GetPaths(string startNodeId, string endNodeId)
        {
            //final paths
            List<Path> pathList = new List<Path>();

            //get all the paths
            GetPath(startNodeId, endNodeId, pathList);

            return pathList;
        }

        /// <summary>
        ///     (Breadth-first algorithm)Gets all the paths from the starting point to the end point
        /// </summary>
        /// <param name="startNodeId">starting point</param>
        /// <param name="endNodeId">end point</param>
        /// <param name="pathList">paths</param>
        private static void GetPath(string startNodeId, string endNodeId, List<Path> pathList)
        {
            //Initializes traveled path
            List<PassedPath> passedPaths = new List<PassedPath>
            {
                new PassedPath(startNodeId, startNodeId, 0)
            };

            //Initializes the node queue
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(Nodes.FirstOrDefault(x => x.Id == startNodeId));

            //loop stop flag
            bool stopFlag = false;

            while (!stopFlag)
            {
                //end the loop when queue is null
                if (queue.Count == 0) break;

                //peek a node from queue
                Node curNode = queue.Peek();

                //continue existing path
                PassedPath passedPath = passedPaths.FirstOrDefault(x => x.NodeId == curNode.Id);

                //remove temp path
                passedPaths.Remove(passedPath);

                if (passedPath != null && curNode.Id == endNodeId && passedPath.PassedRoutes.Length > 1)
                {
                    //add a result path when the current node is the destination
                    pathList.Add(new Path(passedPath.PassedRoutes, passedPath.Distance));

                    //to continue when have a end
                    if (!AppConst.IsFindOtherEndNode)
                    {
                        queue.Dequeue();
                        continue;
                    }
                }

                curNode.EdgeList.ForEach(x =>
                {
                    //marked the traveled path
                    if (passedPath != null)
                        passedPaths.Add(new PassedPath(x.EndNodeId, passedPath.PassedRoutes + x.EndNodeId,
                            passedPath.Distance + x.Weight));

                    //queue add a sub node
                    Node node = Nodes.FirstOrDefault(y => y.Id == x.EndNodeId);
                    queue.Enqueue(node);
                });

                //dequeue currend node
                queue.Dequeue();

                //stop beyond maximum path length
                if (passedPath != null && passedPath.PassedRoutes.Length > AppConst.MaxPathLength) stopFlag = true;
            }
        }
    }
}